/**
 * 回溯算法-迷宫老鼠问题：有一个N * N的矩阵，矩阵的每个位置是一个方块，每个位置
 * 可以是空闲的（值为1）也可以是被阻挡的（值为0），假设(0, 0)是起点，(n-1, n-1)
 * 是终点，找出起始点到终点的具体路径
 * @param maze 迷宫，二维数组，0代表阻碍不能移动到这里，1代表可以移到这里
 */
export function ratInAMaze(maze: number[][]): number[][] {
    // 路径，0代表不在路径中，1代表在路径中
    const solution = [];
    for (let i = 0, ml = maze.length; i < ml; i ++) {
        solution[i] = [];
        for (let j = 0, mil = maze[i].length; j < mil; j ++) {
            solution[i][j] = 0;
        }
    }
    if (findPath(maze, 0, 0, solution)) {
        return solution;
    } else {
        return undefined;
    }
}
/**
 * 寻路
 * @param maze 迷宫（地图）
 * @param x 当前横坐标索引
 * @param y 当前纵坐标索引
 * @param solution 当前路径
 */
const findPath = (maze: number[][], x: number, y: number, solution: number[][]): boolean => {
    const n = maze.length;
    // 当前坐标已经达到终点
    if (x === n - 1 && y === n - 1) {
        solution[x][y] = 1;
        return true;
    }
    // 还没达到终点，需要移动，可以下移，也可以右移
    if (isSafe(maze, x, y)) {
        solution[x][y] = 1;
        // 右移一格
        if (findPath(maze, x + 1, y, solution)) {
            return true;
        }
        // 下移一格
        if (findPath(maze, x, y + 1, solution)) {
            return true;
        }
        // 回溯，右移下移都不行，证明这个位置虽然是空闲的但是没有路可以走了
        solution[x][y] = 0;
        return false; // 需要回溯寻找新路
    }
    // 回溯，移动到当前位置，但是当前位置是有阻碍的，那么回溯找可以移动的
    return false;
};
/**
 * 该地图坐标的这个点是否是空闲的（值为1就是空闲的）
 * @param maze 地图
 * @param x 横坐标
 * @param y 纵坐标
 */
const isSafe = (maze: number[][], x: number, y: number): boolean => {
    const n = maze.length;
    if (x >= 0 && y >= 0 && x < n && y < n && maze[x][y] === 1) {
        return true;
    }
    return false;
};
